<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<p>
  桶排序（也被称为箱排序）也是分布式排序算法，它将元素分为不同的桶（较小的数组），再使用一个简单的排序算法，
  例如插入排序（用来排序小数组的不错的算法），来对每个桶进行排序。然后，它将所有的桶合并为结果数组。
  <br>
  复杂度为 O(n + k)
</p>
<script>
  function bucketSort (arr, bucketSize = 3) {
    if (arr.length <= 1) return arr
    // 创建几个桶
    let buckets = createBuckets(arr, bucketSize)
    // 小桶排序好之后再concat
    let newArr = []
    for (let bucket of buckets) {
      insertSort(bucket)
      newArr = newArr.concat(bucket)
    }
    return newArr
  }

  function createBuckets (arr, bucketSize) {
    const max = Math.max(...arr)
    const min = Math.min(...arr)

    // 桶的数量
    const bucketCount = Math.floor((max - min) / bucketSize) + 1
    // 生成桶
    const buckets = [...Array(bucketCount)].map(() => [])
    // let i = bucketCount
    // while (i > 0) {
    //   buckets.push([])
    //   i --
    // }

    for (let i = 0; i < arr.length; i ++) {
      // 计算放入哪个桶中
      const index = Math.floor((arr[i] - min) / bucketSize)
      // 放入桶中
      buckets[index].push(arr[i])
    }
    return buckets
  }

  // 插入排序（小范围数组排序效率高）
  function insertSort (arr) {
    if (arr.length <= 1) return arr

    let temp
    for (let i = 1; i < arr.length; i ++) {
      temp = arr[i]
      let j = i
      while (j > 0 && arr[j - 1] > temp) {
        arr[j] = arr[j - 1]
        j --
      }
      arr[j] = temp
    }
  }


  const arr = [9, 5, 3, 4, 5, 100, 2, 1, 0]
  // 返回新数组，不改变原数组
  const newArr = bucketSort(arr)
  console.log(newArr)
</script>
</body>
</html>
